﻿#include "stdafx.h"
#include "MergeKSortedLists.h"

using namespace std;

namespace algorithm {
    struct cmp {
        bool operator()(const ListNode* _Left, const ListNode* _Right) const
        {
            return _Left->val > _Right->val;
        }
    };

    ListNode* CMergeKSortedLists::Merge(vector<ListNode*>& lists)
    {
        priority_queue<ListNode*, vector<ListNode*>, cmp> littleHeap;
        vector<ListNode*> headVec;//给传入链表数组每个链表增加头节点，首节点空判断
        for (auto item : lists) {
            ListNode* head = new ListNode;
            head->next = item;
            headVec.push_back(head);
            if (head->next) {
                littleHeap.push(head->next);//将链表头节点放入小堆
            }
        }

        ListNode head;
        ListNode* it = &head;
        while (!littleHeap.empty()) {
            auto node = littleHeap.top();//取小堆头节点，即最小值
            littleHeap.pop();
            it->next = new ListNode(node->val);//放入结果链表
            it = it->next;

            if (node->next) {//如果取出的头节点还有节点，将下一个节点重新放入小堆
                littleHeap.push(node->next);
            }
        }

        for (auto item : headVec) {
            delete item;//释放开始申请的链表头节点内存
        }
        return head.next;
    }
}
